package nonogram;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Line {
	private String id;
	private List<Cell> cells = new ArrayList<>();
	private List<Group> groups = new ArrayList<>();

	// -2 means not assigned yet;
	// -1 means all groups do NOT have the same size.
	private int maxGroupSame = -2;

	// This value is updated every time a cell is set to FILLED or BLANK
	// It is used for some heuristic calculations.
	private int totalUnknownCells = 0;
	private int filledCellsExpected = 0;
	private int blankCellsExpected = 0;
	
	private LineType lineType;
	private boolean solved = false;
	private boolean filledCompletely = false; // no cells are left unknown.

	public Line(String lineId, LineType t, int size) {
		id = lineId;
		lineType = t;

		// Add a starting boundary group.
		Group start = new LeftBoundaryGroup();
		groups.add(start);

		// Add a starting boundary group.
		Group end = new RightBoundaryGroup(size);
		groups.add(end);
	}

	@Override
	public String toString() {
		String str = "|";

		for (Cell cell : cells) {
			str += cell.toString() + "|";
		}

		return str;
	}

	public String toHtml(String tabs) {
		String str = "";

		str += tabs + "<tr>\n";

		for (Cell cell : cells) {
			str += cell.toHtml(tabs + "\t") + "\n";
		}

		str += tabs + "</tr>\n";

		return str;
	}

	public LineType getType() {
		return lineType;
	}

	public void addCell(Cell cell) {
		cells.add(cell);
		totalUnknownCells++;
		blankCellsExpected++;
	}

	public void setCell(int i, CellType type) {
		if (i < 0 || i >= lineSize()) {
			System.err.println("Invalid List index " + i);
			return;
		}

		cells.get(i).setCellType(type);
		if (type != CellType.UNKNOWN) {
			totalUnknownCells--;
		}
	}

	public void addGroup(Group group) {
		groups.add(numberOfGroups() - 1, group);
		// if (allGroupsSameSize == -2) {
		// allGroupsSameSize = group.getSize();
		// }
		// else if (group.getSize() != allGroupsSameSize) {
		// allGroupsSameSize = -1;
		// }

		if (group.getSize() > maxGroupSame) {
			maxGroupSame = group.getSize();
		}
		
		filledCellsExpected += group.getSize();
		blankCellsExpected -= group.getSize();
	}

	/**
	 * Solves the line for all cells and the non-boundary groups.
	 * 
	 * @return The changed indices.
	 */
	public List<Integer> quickLineSolve() {
		return quickLineSolve(0, lineSize(), 1, numberOfGroups() - 1);
	}

	/**
	 * Solves the line between particular cells and groups.
	 * 
	 * @return The changed indices.
	 */
	public List<Integer> quickLineSolve(int startCell, int endCell, int startGroup, int endGroup) {

		List<Cell> cellsToCheck = cells.subList(startCell, endCell);
		List<Group> groupsToCheck = groups.subList(startGroup, endGroup);
		List<Integer> changedIndices = new ArrayList<>();

		int size = lineSize();
		int total = -1;
		for (Group group : groupsToCheck) {
			if (group.getSize() == 0) {
				for (int i = startCell; i < endCell; i++) {
					this.setCell(i, CellType.BLANK);
					changedIndices.add(i);
				}
				group.updateComplete();
				return changedIndices;
			}
			else {
				total += group.getSize() + 1;
			}
		}

		int offset = size - total;

		int cellNum = 0;
		for (Group group : groupsToCheck) {
			if (group.getComplete()) {
				continue;
			}

			int groupValue = group.getSize();
			int diff = (groupValue - offset);

			if (diff <= 0) {
				// Cannot fill anything in.
				cellNum += groupValue; // Skip this groups possible location.
			}
			else {
				cellNum += offset;
				int stop = cellNum + diff;
				for (; cellNum < stop; cellNum++) {
					cellsToCheck.get(cellNum).setCellType(CellType.FILLED);
					changedIndices.add(cellNum);
				}
			}

			cellNum += 1;
		}

		return changedIndices;
	}

	/**
	 * Solves the line as much as possible, taking into account the current
	 * state of the line.
	 * 
	 * @return The changed indices.
	 */
	public List<Integer> lineSolve() {
		List<SubGroup> subGroups = updateCompletedGroups();

		
		List<Integer> changedIndices1 = mergeGroups();
		List<Integer> changedIndices2 = crossOutCellsBetweenGroups();
		List<Integer> changedIndices3 = crossOutCellsNearEdge();
		List<Integer> changedIndices4 = crossOutSubGroupsNotInGroups(subGroups);
		List<Integer> changedIndices5 = fillInCells();

		changedIndices1.addAll(changedIndices2);
		changedIndices1.addAll(changedIndices3);
		changedIndices1.addAll(changedIndices4);
		changedIndices1.addAll(changedIndices5);
		
		return changedIndices1;

	}

	/**
	 * Updates which groups have been completed, to help with line solving.
	 */
	private List<SubGroup> updateCompletedGroups() {
//		for (Group g : this.getActualGroups()) {
//			g.updateComplete();
//		}
		
		List<SubGroup> potentialGroups = findPotentialGroups();

		// TODO: Make sure this function works.		
		updateAlreadyAssignedGroups(potentialGroups);

		assignSubGroups(potentialGroups);

		return potentialGroups;
	}

	/**
	 * Groups the filled in cells together into subgroups that could belong to
	 * the actual groups.
	 * 
	 * @return The potential groups.
	 */
	private List<SubGroup> findPotentialGroups() {
		List<SubGroup> potentialGroups = new ArrayList<>();

		// Calculate the continuous cells actually filled in.
		int count = 0;
		int start = 0;

		for (int i = 0; i < lineSize(); i++) {
			Cell cell = cells.get(i);

			if (cell.getCellType() == CellType.FILLED) {
				if (count == 0) {
					start = i;
				}
				count++;
			}
			else {
				if (count > 0) {
					SubGroup subGroup = new SubGroup(start, start + count);
					// group.setStart(start);
					// group.setEnd(start + count);

					potentialGroups.add(subGroup);
					count = 0;
				}
			}
		}

		if (count > 0) {
			SubGroup subGroup = new SubGroup(start, start + count);
			// group.setStart(start);
			// group.setEnd(start + count);

			potentialGroups.add(subGroup);
		}

		return potentialGroups;
	}
	
	/**
	 * Some of the potential subgroups may already be assigned to groups.
	 * If so remove them. Also, if the subgroup is larger than before, extend the group as well. 
	 * @param potentialGroups
	 */
	public void updateAlreadyAssignedGroups(List<SubGroup> potentialGroups) {
		SubGroup sub;
		int subStart;
		int subEnd;
		int subSize;
		int groupStart;
		int groupEnd;
		int groupSize;
		
		Iterator<SubGroup> it = potentialGroups.iterator();
		while (it.hasNext()) {
			
			sub = it.next();
			subStart = sub.getStart();
			subEnd = sub.getEnd();
			subSize = sub.getSize();
			
			for (Group group : getActualGroups()) {
				groupStart = group.getStart();
				groupEnd = group.getEnd();
				groupSize = group.getSize();
				
				if (subStart <= groupStart && subEnd >= groupEnd && subSize <= groupSize) {
					// Need to update group.
					group.updateSubGroup(0, subStart, subEnd);
					group.updateComplete(); // May have been completed.
					
					it.remove();
					break;
				}
			}
		}
	}

	/**
	 * Determines which potential subgroups, if any, can be assigned to the actual
	 * groups.
	 * 
	 * @param potentialGroups
	 */
	private void assignSubGroups(List<SubGroup> potentialGroups) {

		// The list of groups that each potential subgroup could fit into.
		Map<SubGroup, List<Group>> groupMap = new HashMap<>();
		List<Group> groupsToRemove = new ArrayList<>();
		
		boolean changes = true;
		
		for (int i = 0; i < potentialGroups.size(); i++) {
			List<Group> groups = assignSubGroup(i, potentialGroups);
				groupMap.put(potentialGroups.get(i), groups);
		}

		while (changes) {
			changes = false;
			
			Iterator<SubGroup> it = groupMap.keySet().iterator();
			while (it.hasNext()){
				SubGroup sub = it.next();
				
				List<Group> groups = groupMap.get(sub);
				if (groups.size() == 1) {
					Group group = groups.get(0);
					group.addSubGroup(sub);
					if (group.getSize() == sub.getSize()) {
						group.updateComplete();
					}
					
					it.remove();
					groupsToRemove.add(group);
					changes = true;
				}
			}
			
			for (SubGroup sub : groupMap.keySet()) {
				List<Group> groupsForSub = groupMap.get(sub);
				
				for (Group group : groupsToRemove) {
					if (!group.subGroupsFit(sub, sub)) {
						// Subgroup no longer fits in this group after a different subgroup has been assigned to it.
						groupsForSub.remove(group);
					}
				}
			}
			
			groupsToRemove.clear();
		}

	}

	/**
	 * Determines which actual groups this potential group could be assigned to.
	 * 
	 * @param int indexToCheck
	 * @param potentialGroups
	 * @return
	 */
	private List<Group> assignSubGroup(int indexToCheck, List<SubGroup> potentialGroups) {

		List<Group> groupsToReturn = new ArrayList<>();
		SubGroup potential = potentialGroups.get(indexToCheck);
		List<Group> actualGroups = getActualGroups();

		for (int i = 0; i < actualGroups.size(); i++) {
			Group group = actualGroups.get(i);

			// TODO: Optimize by only checking groups between (inclusive) where the subgroup must be.
			// Do this based on the start and end of those groups, versus the start and end of this subgroup.
			
			if (potential.getSize() <= group.getSize()) {
				if (otherSubGroupsFit(indexToCheck, potentialGroups, i, actualGroups)) {
					groupsToReturn.add(group);

					// TODO: Look into changing this, so that I can check all combinations/intersections.
					// And then can keep statistics for unassigned subgroups to help with solving later.

				}
			}
		}

		return groupsToReturn;
	}
	
	/**
	 * When the given subgroup goes with the given group, can the rest of the
	 * subgroups fit in the rest of the groups.
	 * 
	 * @param potentialIndex
	 * @param potentialGroups
	 * @param groupIndex
	 * @param actualGroups
	 * @return
	 */
	private boolean otherSubGroupsFit(int potentialCheckIndex, List<SubGroup> potentialGroups, int groupCheckIndex,
			List<Group> actualGroups) {
	
		int leftSum = 0;
		for (int i = 0; i < groupCheckIndex; i++) {
			leftSum += actualGroups.get(i).getSize() + 1;
		}

		if (leftSum > potentialGroups.get(potentialCheckIndex).getStart()) {
			return false;
		}

		int rightSum = 0;
		for (int i = actualGroups.size() - 1; i > groupCheckIndex; i--) {
			rightSum += actualGroups.get(i).getSize() + 1;
		}

		if ((this.lineSize() - rightSum) < potentialGroups.get(potentialCheckIndex).getEnd()) {
			return false;
		}

		Group groupCheck = actualGroups.get(groupCheckIndex);
		SubGroup potentialCheck = potentialGroups.get(potentialCheckIndex);

		// This group doesn't fit into the potential group.
		if (!groupCheck.subGroupsFit(potentialCheck, potentialCheck)) {
			return false;
		}

		// ******************************************************************\\
		// Check left hand side.

		int subIndex = 0;
		SubGroup end = potentialGroups.get(subIndex);
		SubGroup start = end;
		Group currentGroup;
		boolean fits;

		int groupIndex = 0;
		currentGroup = actualGroups.get(groupIndex);

		while (subIndex < potentialCheckIndex && groupIndex < groupCheckIndex) {

			end = potentialGroups.get(subIndex);
			currentGroup = actualGroups.get(groupIndex);

			fits = currentGroup.subGroupsFit(start, end);

			if (fits) {
				// Then we want to try to fit the next subgroup in this group as
				// well.
				subIndex++;

			}
			else {
				// Then we want to try to fit only this subgroup into the next
				// group.
				start = end;
				groupIndex++;
			}
		}

		// ******************************************************************\\
		// If left over from left hand side, try to fit them with potentialCheck
		// in groupCheck.

		SubGroup neededForLater;

		if (subIndex != potentialCheckIndex) {
			SubGroup temp = potentialGroups.get(subIndex);
			fits = groupCheck.subGroupsFit(temp, potentialCheck);

			if (!fits) {
				// Then left side cannot fit
				return false;
			}

			neededForLater = temp;
		}
		else {
			neededForLater = potentialCheck;
		}

		// ******************************************************************\\
		// Check right hand side.

		// Note: Many things are reversed from the left hand side, like < and >
		// or flipping the use of start and end.

		subIndex = potentialGroups.size() - 1;
		start = potentialGroups.get(subIndex);
		end = start;

		groupIndex = actualGroups.size() - 1;
		currentGroup = actualGroups.get(groupIndex);

		while (subIndex > potentialCheckIndex && groupIndex > groupCheckIndex) {

			start = potentialGroups.get(subIndex);
			currentGroup = actualGroups.get(groupIndex);
			fits = currentGroup.subGroupsFit(start, end);

			if (fits) {
				// Then we want to try to fit the next subgroup in this group as
				// well.
				subIndex--;
			}
			else {
				// Then we want to try to fit only this subgroup into the next
				// group.
				end = start;
				groupIndex--;
			}
		}

		// ******************************************************************\\
		// If left over from right hand side, try to fit them with
		// potentialCheck (and maybe some from left hand side; neededForLater)
		// in groupCheck.

		if (subIndex != potentialCheckIndex) {
			SubGroup temp = potentialGroups.get(subIndex);
			fits = groupCheck.subGroupsFit(neededForLater, temp);

			if (!fits) {
				// Then left side cannot fit
				return false;
			}
		}

		return true;
	}
	
	/**
	 * Looks at groups that have multiple subgroups. Fills in the cells between
	 * those subgroups.
	 * 
	 * @return The changed indices.
	 */
	private List<Integer> mergeGroups() {
		List<Integer> changedIndices = new ArrayList<>();
		List<Integer> changedForGroup = new ArrayList<>();
		for (Group group : getActualGroups()) {
			changedForGroup = group.mergeSubGroups();

			for (int index : changedForGroup) {
				setCell(index, CellType.FILLED);
			}

			changedIndices.addAll(changedForGroup);
		}

		return changedIndices;
	}

	/**
	 * Crosses out cells which cannot be filled in. Do this by checking between
	 * two consecutive in-progress groups, to find what cannot be reached.
	 * 
	 * @return The changed indices.
	 */
	private List<Integer> crossOutCellsBetweenGroups() {
		List<Integer> changedIndices = new ArrayList<>();

		int size = this.numberOfGroups();
		Group first;
		Group second;
		int startIndex;
		int endIndex;

		// If group is complete, cross out the cells next to it.
		for (Group group : this.getActualGroups()) {
			if (group.getJustCompleted()) {
				group.setNotJustCompleted();

				int idx1 = group.getStart() - 1;
				int idx2 = group.getEnd();

				if (idx1 > 0 && this.cellIsType(idx1, CellType.UNKNOWN)) {
					this.setCell(idx1, CellType.BLANK);
					changedIndices.add(idx1);
				}

				if (idx2 < this.lineSize() && this.cellIsType(idx2, CellType.UNKNOWN)) {
					this.setCell(idx2, CellType.BLANK);
					changedIndices.add(idx2);
				}
			}
		}

		for (int i = 0; i < size - 1; i++) {
			second = groups.get(i + 1);
			if (!second.inProgressOrComplete()) {
				i++; // Skip this one completely.
				continue;
			}

			first = groups.get(i);
			if (!first.inProgressOrComplete()) {
				continue;
			}

			startIndex = first.getEnd() + first.getSize() - first.getSubGroupSize();
			endIndex = second.getStart() - second.getSize() + second.getSubGroupSize();

			for (int j = startIndex; j < endIndex; j++) {

				// Only update and add to changed indices if it was actually
				// changed.
				if (this.cellIsType(j, CellType.UNKNOWN)) {
					this.setCell(j, CellType.BLANK);
					changedIndices.add(j);
				}
			}

		}

		return changedIndices;
	}
	
	/**
	 * Cross out cells near the boarder which cannot be filled in.
	 * This is done by finding seeing if the first group fits all the way from the left.
	 * @return
	 */
	private List<Integer> crossOutCellsNearEdge() {
		List<Integer> changedIndices = new ArrayList<>();
		List<Group> groups = this.getActualGroups();
		
		// Left side
		Group group = groups.get(0);
		int size = group.getSize();
		int cellNum = 0;
		int firstBlank = cellNum;

		while (size > 0 && cellNum < this.lineSize()) {
			if (this.cellIsType(cellNum, CellType.BLANK)) {
				size = group.getSize();
				
				for (int i = firstBlank; i < cellNum; i++) {
					this.setCell(i, CellType.BLANK);
					changedIndices.add(i);
				}
				
				firstBlank = cellNum + 1;
			}
			else {
				size--;
				
				if (size == group.getSize() - 1) {
					firstBlank = cellNum;
				}
			}
			
			cellNum++;
		}
		
		
		// Right side
		group = groups.get(groups.size() - 1);
		size = group.getSize();
		cellNum = this.lineSize() - 1;
		firstBlank = cellNum;
		
		while (size > 0 && cellNum >= 0) {
			if (this.cellIsType(cellNum, CellType.BLANK)) {
				size = group.getSize();
				
				for (int i = firstBlank; i > cellNum; i--) {
					this.setCell(i, CellType.BLANK);
					changedIndices.add(i);
				}
				
				firstBlank = cellNum - 1;
			}
			else {
				size--;
				
				if (size == group.getSize() - 1) {
					firstBlank = cellNum;
				}
			}
			
			cellNum--;
		}
		
		
		return changedIndices;
	}

	/**
	 * Crossed out cells around subgroups not assigned to groups.
	 * @param subGroups
	 * @return
	 */
	private List<Integer> crossOutSubGroupsNotInGroups(List<SubGroup> subGroups) {
		// TODO: Add to subgroups a variable for the min and max possible groups
		// that it could be assigned to.
		
		List<Integer> changedIndices = new ArrayList<>();
		if (maxGroupSame > 0) {
			int crossLeft;
			int crossRight;

			for (SubGroup sub : subGroups) {
				if (sub.getSize() != maxGroupSame) {
					// Cannot cross out around this incomplete subgroup.
					continue;
				}

				crossLeft = sub.getStart() - 1;
				crossRight = sub.getEnd();

				if (crossLeft >= 0 && cells.get(crossLeft).getCellType() == CellType.UNKNOWN) {
					this.setCell(crossLeft, CellType.BLANK);
					changedIndices.add(crossLeft);
				}

				if (crossRight < this.lineSize() && cells.get(crossRight).getCellType() == CellType.UNKNOWN) {
					this.setCell(crossRight, CellType.BLANK);
					changedIndices.add(crossRight);
				}
			}
		}

		return changedIndices;
	}
	
	/**
	 * Fills in known cells.
	 * 
	 * @return The changed indices.
	 */
	private List<Integer> fillInCells() {
		// TODO: Note: If two groups are complete (almost complete?) then we can
		// run quickSolve between those groups as if it were a sub-line.
		
		List<Integer> changedIndices1 = fillInCellsByExtending();
		List<Integer> changedIndices2 = fillInCellsByFindingOpenings();
		
		changedIndices1.addAll(changedIndices2);
		
		return changedIndices1;
	}

	/**
	 * Fills in more cells, by trying to extend currently filled in cells..
	 * 
	 * @return The changed indices.
	 */
	private List<Integer> fillInCellsByExtending() {
		List<Integer> changedIndices = new ArrayList<>();

		Group group;
		int leftStop;
		int rightStop;
		
		// The last positions that don't overlap with other known groups.
		Group lastLeftFilledGroup = this.getLeftBoundaryGroup();
		int lastLeftSafe = lastLeftFilledGroup.getSafeAfterEnd();
		int lastRightSafe;

		for (int i = 1; i < this.numberOfGroups() - 1; i++) {
			group = groups.get(i);
			
			if (group.getComplete()) {
				// Update the left filled group and its position.
				lastLeftFilledGroup = group;
				lastLeftSafe = lastLeftFilledGroup.getSafeAfterEnd();
				continue;
			}
			else if (!group.inProgress()) {
				// Skip over the bare minimum cells needed to fill this unstarted cells.
				lastLeftSafe += group.getSize() + 1;
				continue;
			}

			lastRightSafe = this.getLastSafeCellAfter(i);
			
			// Shift the stopping points if there is a blank in the way.			
			leftStop = lastLeftSafe;
			rightStop = lastRightSafe;
			
			for (int j = group.getStart() - 1; j >= lastLeftSafe; j--) {
				if (this.cellIsType(j, CellType.BLANK)) {
					leftStop = j + 1;
					break;
				}
			}
			
			for (int j = group.getEnd(); j <= lastRightSafe; j++) {
				if (this.cellIsType(j, CellType.BLANK)) {
					rightStop = j - 1;
					break;
				}
			}

			int size = rightStop - leftStop + 1;
			int diff = size - group.getSize();

			for (int j = leftStop + diff; j < group.getStart(); j++) {
				// Update if not already filled.
				if (!this.cellIsType(j, CellType.FILLED)) {
					this.setCell(j, CellType.FILLED);
					changedIndices.add(j);
				}
			}

			for (int j = rightStop - diff; j >= group.getEnd(); j--) {
				// Update if not already filled.
				if (!this.cellIsType(j, CellType.FILLED)) {
					this.setCell(j, CellType.FILLED);
					changedIndices.add(j);
				}
			}	
			
			// Set for next group being checked.
			lastLeftFilledGroup = group;
			lastLeftSafe = lastLeftFilledGroup.getSafeAfterEnd();
		}
		
		return changedIndices;
	}
	
	/**
	 * The position to the right of group i that is safe.
	 * @param i The group index to start searching after.
	 * @return farthest right from the group to go safely.
	 */
	private int getLastSafeCellAfter(int i) {
		int offset = 0;
		Group rightGroup = this.getRightBoundaryGroup();
		for (int j = i + 1; j < this.numberOfGroups(); j++) {
			Group group = groups.get(j);
			if (group.inProgressOrComplete()) {
				rightGroup = group;
				break;
			}
			else {
				offset += group.getSize() + 1;
			}
		}
		
		// Should never get here.
		return rightGroup.getSafeBeforeStart() - offset;
	}
	
	/**
	 * Similar to quick line solving, but accounts for blank cells.
	 * 
	 * @return The changed indices.
	 */
	private List<Integer> fillInCellsByFindingOpenings() {
		List<Integer> changedIndices = new ArrayList<>();
		
		int unassigned = -1;
		
		int leftSolved = unassigned;
		int rightSolved = unassigned;
		int startUnsolved = unassigned;
		int endUnsolved = unassigned;
		
		Group group;
		for (int i = 0; i < groups.size(); i++) {
			group = groups.get(i);
			
			if (group.inProgressOrComplete()) {
				if (leftSolved == unassigned || startUnsolved == unassigned) {
					leftSolved = i;
				}
				else {
					rightSolved = i;
				}
			}
			else {
				if (startUnsolved == unassigned) {
					startUnsolved = i;
				}
				endUnsolved = i;
			}
			
			if (rightSolved != unassigned) {
				List<Integer> partialChangedIndices = fillBetweenGroups(
						groups.get(leftSolved).getSafeAfterEnd(),
						groups.get(rightSolved).getSafeBeforeStart(),
						startUnsolved, endUnsolved);
				
				changedIndices.addAll(partialChangedIndices);
				
				// Reset for next iteration
				leftSolved = rightSolved;
				rightSolved = unassigned;
				startUnsolved = unassigned;
				endUnsolved = unassigned;
			}
		}
		
		return changedIndices;
	}
	
	private List<Integer> fillBetweenGroups(int startCell, int endCell, int startGroup, int endGroup) {
		List<Integer> changedIndices = new ArrayList<>();
		
		// TODO: Account for already filled in cells (that aren't in groups).
		
		List<SubGroup> fromLeft = new ArrayList<>();
		List<SubGroup> fromRight = new ArrayList<>();
		
		// Find left groupings
		int groupNum = startGroup;
		Group group = groups.get(groupNum);
		int size = group.getSize();
		SubGroup currentSubGroup = new SubGroup(-1, -1);	
		
		for (int i = startCell; i <= endCell && groupNum <= endGroup; i++) {
			if (cellIsType(i, CellType.BLANK)) {
				// Skip blank, reset size, and reset subgroup.
				size = group.getSize();
				currentSubGroup.setStart(-1);
			}
			else if (cellIsType(i, CellType.UNKNOWN) || cellIsType(i, CellType.FILLED)) {
				size--;
				if (size == group.getSize()-1) {
					// new group started.
					currentSubGroup.setStart(i);
				}
				if (size == 0) {
					// Add and reset subgroup.
					currentSubGroup.setEnd(i + 1);
					fromLeft.add(currentSubGroup);
					currentSubGroup = new SubGroup(-1, -1);
					
					// Go to next group.
					groupNum++;
					group = groups.get(groupNum);
					size = group.getSize();
					
					// Skip next cell, since it cannot be filled.
					i++;
				}
			}
		}
		
		
		// Find right groupings
		groupNum = endGroup;
		group = groups.get(groupNum);
		size = group.getSize();
		currentSubGroup = new SubGroup(-1, -1);
				
		for (int i = endCell; i >= startCell && groupNum >= startGroup; i--) {
			if (cellIsType(i, CellType.BLANK)) {
				// Skip blank, reset size, and reset subgroup.
				size = group.getSize();
				currentSubGroup.setEnd(-1);
			}
			else if (cellIsType(i, CellType.UNKNOWN) || cellIsType(i, CellType.FILLED)) {
				size--;
				if (size == group.getSize() - 1) {
					// new group started.
					currentSubGroup.setEnd(i+1);
				}
				if (size == 0) {
					// Add and reset subgroup.
					currentSubGroup.setStart(i);
					fromRight.add(0, currentSubGroup); // add to beginning to get same order as fromLeft
					currentSubGroup = new SubGroup(-1, -1);

					// Go to next group.
					groupNum--;
					group = groups.get(groupNum);
					size = group.getSize();

					// Skip next cell, since it cannot be filled.
					i--;
				}
			}
		}
		
		SubGroup sub;
		Group groupToUpdate;
		for (int i = 0; i < fromLeft.size(); i++) {
			if (fromLeft.size() != fromRight.size()) {
				break;
			}
			sub = fromLeft.get(i).intersect(fromRight.get(i));
			if (sub.getStart() != -1) {
				groupToUpdate = groups.get(startGroup + i);
				groupToUpdate.addSubGroup(sub);
				
				for (int j = sub.getStart(); j < sub.getEnd(); j++) {
					this.setCell(j, CellType.FILLED);
					changedIndices.add(j);
				}
			}
			
		}

		return changedIndices;
	}

	public boolean isSolved() {
		if (solved) {
			return solved;
		}

		updateSolved();
		return solved;
	}

	public boolean isFilledCompletely() {
		if (filledCompletely) {
			return filledCompletely;
		}

		for (Cell cell : cells) {
			if (cell.getCellType() == CellType.UNKNOWN) {
				return filledCompletely;
			}
		}

		filledCompletely = true;
		return filledCompletely;
	}

	public String getId() {
		return id;
	}

	public void updateSolved() {
		List<Group> actualGroups = getActualGroups();

		int size = actualGroups.size();

		// Line is an empty (zero) line.
		if (size == 0 || actualGroups.get(0).getSize() == 0) {
			solved = true;
			return;
		}

		// Creates groups from the current state of the line.
		List<Group> checkGroups = new ArrayList<>();
		int groupLength = 0;
		for (Cell cell : cells) {
			CellType type = cell.getCellType();

			if (type == CellType.FILLED) {
				groupLength++;
			}
			else {
				if (groupLength > 0) {
					checkGroups.add(new Group(groupLength));
					groupLength = 0;
				}
			}
		}

		if (groupLength > 0) {
			checkGroups.add(new Group(groupLength));
		}

		// Compare the require groups with the ones compiled from the state of
		// the line.
		if (size != checkGroups.size()) {
			return;
		}

		for (int i = 0; i < size; i++) {
			int groupValue = actualGroups.get(i).getSize();
			int checkGroupValue = checkGroups.get(i).getSize();

			if (groupValue != checkGroupValue) {
				return;
			}
		}

		// Line matches required groups completely.
		solved = true;
	}

	/**
	 * Determines the heuristic value for line solving.
	 * 
	 * @return The calculated heuristic value.
	 */
	public int getLineHeuristic() {
		return staticBlankNumberHeuristic();
//		return staticFilledNumberHeuristic();
		
//		return numberUnknownCellHeuristic();
//		return numberKnownCellHeuristic();


		// Don't use these.
//		return numberUnfilledHeuristic();
//		return numberFilledHeuristic();
	}

	// *** A bunch of heuristics to compare runtimes with. ***//

	/**
	 * A static heuristic that returns the number of blank cells expected for the line.
	 * 
	 * @return The heuristic value.
	 */
	private int staticBlankNumberHeuristic() {
		return blankCellsExpected;
		
		// In line calculation no longer needed.
//		int value = lineSize();
//		for (Group group : getActualGroups()) {
//			value -= group.getSize();
//		}
//
//		return value;

	}
	
	/**
	 * A static heuristic that returns the number of filled cells expected for the line.
	 * 
	 * @return The heuristic value.
	 */
	private int staticFilledNumberHeuristic() {
		return filledCellsExpected;
		
		// In line calculation no longer needed.
//		int value = 0;
//		for (Group group : getActualGroups()) {
//			value += group.getSize();
//		}
//
//		return value;	

	}
	
	/**
	 * A heuristic returns the number of group cells that have not been filled.
	 * 
	 * @return The heuristic value.
	 */
	private int numberUnfilledHeuristic() {
		int value = 0;
		for (Group group : getActualGroups()) {
			value += group.getSize();
			int knownCells = group.getSubGroupSize();
			if (knownCells != -1) {
				value -= knownCells;
			}
		}

		return value;
	}
	
	/**
	 * A heuristic returns the number of group cells that have been filled.
	 * 
	 * @return The heuristic value.
	 */
	private int numberFilledHeuristic() {
		int value = 0;
		for (Group group : getActualGroups()) {
			int knownCells = group.getSubGroupSize();
			if (knownCells != -1) {
				value += knownCells;
			}
		}

		return value;
	}

	/**
	 * A heuristic returns the number of cells that are unknown.
	 * 
	 * @return The heuristic value.
	 */
	private int numberUnknownCellHeuristic() {
		// This value is updated every time a cell is set to FILLED or BLANK
		return totalUnknownCells;
		
		// In line calculation no longer needed.
//		int value = 0;
//		for (int i = 0; i < this.lineSize(); i++) {
//			if (this.cellIsType(i, CellType.UNKNOWN)) {
//				value++;
//			}
//		}
//
//		return value;
	}
	
	/**
	 * A heuristic returns the number of cells that are known.
	 * 
	 * @return The heuristic value.
	 */
	private int numberKnownCellHeuristic() {
		// This value is updated every time a cell is set to FILLED or BLANK
		return this.lineSize() - totalUnknownCells;
		
		// In line calculation no longer needed.
//		int value = 0;
//		for (int i = 0; i < this.lineSize(); i++) {
//			if (!this.cellIsType(i, CellType.UNKNOWN)) {
//				value++;
//			}
//		}
//
//		return value;
	}

	public List<Group> getActualGroups() {
		return groups.subList(1, groups.size() - 1);
	}
	
	public Group getLeftBoundaryGroup() {
		return groups.get(0);
	}
	
	public Group getRightBoundaryGroup() {
		return groups.get(groups.size()-1);
	}

	public int lineSize() {
		return cells.size();
	}

	public int numberOfGroups() {
		return groups.size();
	}
	
	public CellType getCellType(int i) {
		return cells.get(i).getCellType();
	}
	
	public boolean cellIsType(int i, CellType type) {
		return this.getCellType(i) == type;
	}

}
